package algocasts;

import java.util.ArrayList;
import java.util.List;

public class P123_FlattenBinaryTreeToLinkedList {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    private void preorder(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        list.add(root);
        preorder(root.left, list);
        preorder(root.right, list);
    }

    // Time: O(n)  Space: O(n)
    public void flatten_Preorder(TreeNode root) {
        if (root == null) return;
        List<TreeNode> list = new ArrayList<>();
        preorder(root, list);
        TreeNode cur = root;
        for (int i = 1; i < list.size(); i++) {
            cur.left = null;
            cur.right = list.get(i);
            cur = cur.right;
        }
    }

    private TreeNode prev = null;

    // Time: O(n) Space: O(n)
    public void flatten_ReversePreorder(TreeNode root) {
        if (root==null)return;
        flatten_ReversePreorder(root.right);
        flatten_ReversePreorder(root.left);
        root.left = null;
        root.right = prev;
        prev = root;
    }
}
